package DataStructure.tree;

import java.util.LinkedList;

/**
 * 101. 对称二叉树 https://leetcode.cn/problems/symmetric-tree
 * 题目简述：给你一个二叉树的根节点 root，检查它是否关于中心轴对称。
 */
public class IsSymmetric {

    /**
     * 思路一：递归。处于对称位置的两个节点它们的父节点一定也是对称节点，反过来说，一对对称节点它们的孩子节点也为对称节点，
     * 因此根据这样的关系从根节点的左右孩子比较然后递归比较（左孩子的左孩子，右孩子的右孩子）&& （左孩子的左孩子，右孩子的右孩子）即可遍历所有的对称节点
     */
    public boolean isSymmetric(TreeNode root) {
        return root == null || fs(root.left, root.right);
    }
    boolean fs(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;

        return fs(left.left, right.right) && fs(left.right, right.left);
    }

    /**
     * 思路二：迭代法。使用LinkedList作为队列（元素可以为null），首先将根节点的两个孩子节点入队，然后在每次循环中出队两个元素，比较这两个对称元素是否相等，
     * 并依次将（左孩子的左孩子，右孩子的右孩子）和（左孩子的左孩子，右孩子的右孩子）入队，即保证队列中连续的每对元素在树中的位置都是镜像对称的
     */
    public boolean isSymmetric2(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return true;
        //LinkedList元素可以为null
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        //一次循环中出队一对元素，入队两对元素
        while(!queue.isEmpty()) {
            TreeNode u = queue.remove();
            TreeNode v = queue.remove();
            if(u == null && v == null) continue;
            if(u == null || v == null || u.val != v.val) return false;

            queue.add(u.left);
            queue.add(v.right);

            queue.add(u.right);
            queue.add(v.left);
        }
        return true;
    }
}
